//
// Created by 刘振舟 on 2024/3/18.
//
#include <stdio.h>
#include <stdlib.h>


int binarySearchWithBoundary(int *nums, int numsSize, int target, int isLeftBoundary);

int search(int* nums, int numsSize, int target) {
    int left = 0, right = numsSize - 1;
    while (left <= right) {
        int middle = left + ((right - left) >> 1);
        if (nums[middle] == target) {
            return middle;
        } else if (nums[middle] > target) {
            right = middle - 1;
        } else {
            left = middle + 1;
        }
    }
    return -1;
}

int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
    int leftBoundIndex = binarySearchWithBoundary(nums, numsSize, target, 1);
    int rightBoundIndex = binarySearchWithBoundary(nums, numsSize, target, 0);
    int* result = calloc(2, sizeof numsSize);
    *returnSize = 2;
    if (leftBoundIndex > rightBoundIndex || leftBoundIndex < 0 || rightBoundIndex == numsSize) {
        result[0] = -1;
        result[1] = -1;
    } else {
        result[0] = leftBoundIndex;
        result[1] = rightBoundIndex;
    }
    return result;
}

int binarySearchWithBoundary(int *nums, int numsSize, int target, int isLeftBoundary) {
    int left = 0, right = numsSize - 1;
    int ans = -1, middle;
    while (left <= right) {
        middle = left + ((right - left) >> 1);
        if (isLeftBoundary) {
            if (nums[middle] >= target) {
                ans = middle;
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        } else {
            if (nums[middle] <= target) {
                ans = middle;
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
    }
    return ans;
}